//字符串a删除一个字符等效于字符串b添加一个字符，b同理
//字符串a修改一个字符等效于字符串b修改一个字符，b同理
//因此可以分为三种情况：
    //字符串a删除一个字符
    //字符串b删除一个字符
    //字符串a修改一个字符

//dp[i][j]表示字符串a以i结尾的子串和字符串b以j为结尾的子串的最小编辑距离
//如果s1[i] == s2[j]，则dp[i][j] == dp[i - 1][j - 1]
//如果s1[i] != s2[j]
    //如果字符串a删除结尾字符，那么就是字符串a以(i - 1)结尾的子串和字符串b以j结尾的子串的最小编辑距离 + 1
    //如果字符串b删除结尾字符，那么就是字符串a以i结尾的子串和字符串b以(j - 1)结尾的子串的最小编辑距离 + 1
    //如果是字符串a修改结尾字符，那么就是花费一次操作将情况变成（s1[i] == s2[j]），即 dp[i][j] == dp[i - 1][j - 1] + 1
class Solution {
public:
    int minDistance(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        if (m * n == 0)
            return m + n;

        vector<vector<short>> dp(m + 1, vector<short>(n + 1, 0));
        s1 = " " + s1;
        s2 = " " + s2;
        //初始化dp表
        //当i=0时，可以看作s1为空串
        //当j=0时，可以看作s2为空串
        for (int i = 0; i < n + 1; i++)
            dp[0][i] = i;
        for (int j = 0; j < m + 1; j++)
            dp[j][0] = j;

        for (int i = 1; i < m + 1; i++)
        {
            for (int j = 1; j < n + 1; j++)
            {
                if (s1[i] == s2[j])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
            }
        }

        return dp[m][n];
    }
};